10067 - Playing with wheels/10067.2.cpp

   1 #include <iostream>
   2 #include <queue>
   3 #include <vector>
   4 #include <sstream>
   5
   6
   7 using namespace std;
   8
   9 int main(){
  10   int cases;
  11   cin >> cases;
  12   while (cases--){
  13     vector<bool> forbidden(10000, false);
  14     vector<bool> visited(10000, false);
  15
  16
  17     int start = 0;
  18     for (int i=0; i<4; ++i){
  19       int x; scanf("%d", &x);
  20       start = (start * 10) + x;
  21     }
  22
  23     int end = 0;
  24     for (int i=0; i<4; ++i){
  25       int x; scanf("%d", &x);
  26       end = (end * 10) + x;
  27     }
  28
  29     int n;
  30     cin >> n;
  31     while (n--){
  32       int f=0;
  33       for (int i=0; i<4; ++i){
  34         int x; scanf("%d", &x);
  35         f = (f * 10) + x;
  36       }
  37       forbidden[f] = true;
  38     }
  39
  40     queue<pair<int, int> > q;
  41     int answer = -1;
  42     q.push(make_pair(start, 0));
  43     while (!q.empty()){
  44       int node = q.front().first;
  45       int dist = q.front().second;
  46       q.pop();
  47       if (forbidden[node] || visited[node]){
  48         continue;
  49       }
  50       if (node == end){
  51         answer = dist;
  52         break;
  53       }
  54       //cout << "visited["<<node<<"] = " << (visited[node]?"true":"false") << endl;
  55       visited[node] = true;
  56       for (int i=1; i<=4; ++i){
  57         int pow10 = 1; for (int j=1; j<=i; ++j) pow10 *= 10;
  58         int digit = (node % pow10)* 10/pow10;
  59
  60         int v = node - digit * pow10/10;
  61         //cout << "digit es: " << digit << endl;
  62         //cout << "node es: " << node << endl;
  63         //cout << "v es: " << v << endl << endl;
  64         int x = v + pow10/10 * ((digit+1)%10);
  65         int y = v + pow10/10 * ((digit+9)%10);
  66
  67         //cout << "Los vecinos:" << endl;
  68         //cout << x << endl << y << endl;
  69         //cout << endl;
  70
  71         //      if (forbidden[x] == false && visited[x] == false){
  72           q.push(make_pair(x, dist + 1));
  73           //}
  74           //if (!forbidden[y] && !visited[y]){
  75           q.push(make_pair(y, dist + 1));
  76           //}
  77
  78       }
  79     }
  80     cout << answer << endl;
  81
  82   }
  83   return 0;
  84 }